package zcw.com.lib_leet_code;

import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/7/13.<br><br>
 *
 * 只出现一次的数字 III
 */
public class Topic260 {

    public static void main(String[] args) {
        Topic260 instance = new Topic260();

        int[] array = new int[] {1,2,1,3,2,5};
        Util.printArray(instance.singleNumber(array));

        array = new int[] {-1,0};
        Util.printArray(instance.singleNumber(array));

        array = new int[] {0,1};
        Util.printArray(instance.singleNumber(array));
    }

    public int[] singleNumber(int[] nums) {
        int[] result = new int[2];

        int sum = 0;
        for(int value : nums) {
            sum = sum ^ value;
        }

        int flag = sum & (-sum);

        for(int value : nums) {
            if((value & flag) == 0) {
                result[0] = result[0] ^ value;
            }
            else {
                result[1] = result[1] ^ value;
            }
        }

        return result;
    }

    public int[] singleNumber2(int[] nums) {
        int[] result = new int[2];

        int sum = 0;
        for(int value : nums) {
            sum = sum ^ value;
        }

        int flag = 1;
        while ((sum & flag) == 0) {
            flag = flag << 1;
        }

        for(int value : nums) {
            if((value & flag) == 0) {
                result[0] = result[0] ^ value;
            }
            else {
                result[1] = result[1] ^ value;
            }
        }

        return result;
    }
}
